package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//
// Created by ✎﹏ℳ๓独赏☆独醉 on 2024/5/15.
//
//https://leetcode.cn/problems/combination-sum/submissions/532038970/
public class 组合总数 {
    public static void main(String[] args) {
        int[] candidates = {2,3,6,7};
        int target = 7;
        List<List<Integer>> res = combinationSum(candidates,target);
        System.out.println(res);
    }
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
//        boolean[] flag = new boolean[candidates.length];
        Arrays.sort(candidates);
        List<Integer> temp = new ArrayList<>();
        getRes(candidates, target, res,temp,0, 0);
        return res;
    }

    private static void getRes(int[] candidates, int target, List<List<Integer>> res ,List<Integer> temp,int ti, int step) {
        for (int i = ti;i < candidates.length;i++) {
            if (target - candidates[i] > 0) {
                temp.add(candidates[i]);
                getRes(candidates, target - candidates[i], res, temp,i,step + 1);
                temp.remove(step);
            }
            if (target - candidates[i] == 0) {
                temp.add(candidates[i]);
                List<Integer> t = new ArrayList<>(temp);
                res.add(t);
                temp.remove(step);
                break;
            }
            if (target - candidates[i] < 0) {
                break;
            }
        }
    }
}
